/*
Source : https://leetcode.com/problems/reverse-integer/
Author : nflush@outlook.com
Date   : 2016-05-09
*/
/*
12. Integer to Roman  
Total Accepted: 63769 Total Submissions: 163432 Difficulty: Medium

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

Subscribe to see which companies asked this question
*/

char* intToRoman(int num) {
    char *str1000[] = {"", "M", "MM", "MMM"};
    char *str0100[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
    char *str0010[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
    char *str0001[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
    char *ret = malloc(12); // 3888 + '\0'
    sprintf(ret, "%s%s%s%s", 
        str1000[num/1000], 
        str0100[(num/100)%10], 
        str0010[(num/10)%10], 
        str0001[num%10]);
    return ret;
}

char* intToRoman(int num) {
    const char *str1000[] = {"", "M", "MM", "MMM"};
    const char *str0100[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
    const char *str0010[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
    const char *str0001[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
    const int   len[] = {0, 1, 2, 3, 2, 1, 2, 3, 4, 2};
    static char ret[12]; // 3888 + '\0'
    char *pc = ret;
    int x = 1000;
    if (num >= 1000){
        x = num/1000;
        num = num*1000;
        memcpy(pc, str1000[x], len[x]);
        pc += len[x];
    }

    if (num >= 100){
        x = num/100;
        num = num*100;
        memcpy(pc, str0100[x], len[x]);
        pc += len[x];
    }

    if (num >= 10){
        x = num/10;
        num = num*10;
        memcpy(pc, str0010[x], len[x]);
        pc += len[x];
    }

    if (num > 0){
        memcpy(pc, str0001[num], len[num]);
        pc += len[num];
    }
    *pc = 0;

    return ret;
}

